#include "dijkstra.h"
#include <limits>
#include <queue>
#include <vector>

// 使用Dijkstra算法计算从起点start到终点end的最短路径和距离
// distanceMatrix: 距离矩阵，表示图中各节点之间的距离
// start: 起点节点索引
// end: 终点节点索引
// 返回值：QPair包含两个元素，
//         第一个元素是从start到end的最短距离，
//         第二个元素是最短路径经过的节点索引列表
QPair<double, QVector<int>> dijkstra(const QVector<QVector<double>> &distanceMatrix, int start, int end) {
    int n = distanceMatrix.size();  // 节点的总数
    QVector<double> dist(n, std::numeric_limits<double>::infinity());  // 记录从起点到各节点的最短距离，初始为正无穷大
    QVector<int> prev(n, -1);  // 记录路径中每个节点的前驱节点，初始为-1表示无前驱
    QVector<bool> visited(n, false);  // 记录节点是否已被访问过
    dist[start] = 0;  // 起点到自身的距离为0

    // 使用最小堆(priority_queue)来维护当前未访问节点中具有最小距离的节点
    using Node = QPair<double, int>;  // Node类型表示(当前最短距离, 节点索引)
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> minHeap;
    minHeap.push(qMakePair(0.0, start));  // 将起点加入堆中，距离为0

    // 开始算法主循环
    while (!minHeap.empty()) {
        double minDist = minHeap.top().first;  // 堆顶元素的最小距离
        int u = minHeap.top().second;  // 堆顶元素对应的节点索引
        minHeap.pop();  // 将堆顶元素移除

        if (visited[u]) continue;  // 如果该节点已经被访问过，则跳过
        visited[u] = true;  // 标记该节点为已访问

        // 一旦找到终点，立即退出循环
        if (u == end) break;

        // 遍历所有与节点u相邻的节点v
        for (int v = 0; v < n; ++v) {
            // 如果节点v未被访问过且u到v的边存在(距离不为无穷大)
            if (!visited[v] && distanceMatrix[u][v] != std::numeric_limits<double>::infinity()) {
                double newDist = dist[u] + distanceMatrix[u][v];  // 计算经过u到达v的距离
                if (newDist < dist[v]) {  // 如果新计算的距离小于当前记录的距离
                    dist[v] = newDist;  // 更新最短距离
                    prev[v] = u;  // 更新前驱节点
                    minHeap.push(qMakePair(newDist, v));  // 将更新后的节点v加入堆中
                }
            }
        }
    }

    // 通过前驱节点数组prev来构建从start到end的路径
    QVector<int> path;
    for (int at = end; at != -1; at = prev[at]) {  // 从end回溯到start
        path.prepend(at);  // 将节点加入路径，使用prepend从前面插入
    }

    // 如果路径的起点不是start，说明没有有效路径
    if (path[0] != start) {
        path.clear();  // 无路径存在时，清空路径
    }

    // 返回最短距离和路径
    return qMakePair(dist[end], path);
}

